package priority_queue;

import java.util.Arrays;

// 优先级队列 堆
public class TestHeap {
    public int[] elem;
    public int usedSize;
    public TestHeap(){
        this.elem = new int[10];
    }

    // 初始化数组
    public void initElem(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            this.usedSize++;
        }
    }
    public void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    // 创建堆 最大堆
    public void createHeap(){
        for (int parent = (this.usedSize - 1 - 1) / 2; parent >= 0 ; parent--) {
            siftDown(parent,this.usedSize);
        }
    }

    // 向下调整创建堆 从上往下走 每一个子树都是一个大根堆 根据双亲节点确定孩子节点
    // usedSize 是最后一个节点的下一个 调整时不包含下标为 usedSize 的节点
    public void siftDown(int parent,int usedSize){
        int child = parent * 2 + 1;
        while(child < usedSize){
            if(child + 1 < usedSize && elem[child] < elem[child + 1]){
                child++;
            }
            if(elem[parent] < elem[child]){
                swap(elem,parent,child);
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }

    // 插入元素
    // 将语速放在最后的位置 然后进行调整
    public void offer(int val){
        if(isFull()){
            elem = Arrays.copyOf(elem,2 * elem.length);
        }
        elem[usedSize] = val;
        siftUp(usedSize);
        usedSize++;
    }
    public boolean isFull(){
        return usedSize == elem.length;
    }

    // 向上调整创建堆 从下往上走 根据孩子节点确定双亲节点
    public void siftUp(int child){
        int parent = (child - 1) / 2;
        while(parent >= 0){
            if(elem[child] > elem[parent]){
                swap(elem,child,parent);
                child = parent;
                parent = (child - 1) / 2;
            }else{
                break;
            }
        }
    }

    // 删除堆顶元素
    public int poll(){
        if(isEmpty()){
            return -1;
        }
        int val = elem[0];
        swap(elem,0,usedSize - 1);
        // 此时堆顶元素在最后一个位置 也就是usedSize位置 但是该节点不参与调整的过程 多以为 usedSize - 1
        siftDown(0,usedSize - 1);
        // 删除一个元素之后 usedSize 进行 - 1
        usedSize--;
        return val;
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }

    // 查看堆顶元素 堆顶元素就是elem数组中的第一个元素
    public int peek(){
        if(isEmpty()){
            return -1;
        }
        return  elem[0];
    }

    // 让数组从小到大排序
    // 从小到大排序 就要建立大根堆
    public void heapSort(){
        int end = usedSize - 1;
        while(end > 0){
            // 把最后一个元素和堆顶元素进行交换 然后进行调整 大根堆本来堆顶元素是最大的 现在放在最后
            // 进行循环 倒数第二个就是第二个 以此类推......
            // 一直用堆顶元素和end指向的元素进行交换
            // 每交换一次就进行一次调整 保证交换之后的堆 是一个最大堆
            // 直到 end = 0 时 循环结束 这个时候排序也就结束
            swap(elem,0,end);
            // 此处 问 那如果另一棵子树不是大根堆怎么办？？
            // 其实没关系 先从最后一个节点调整 随着 end-- 那么所有节点都会被走一遍 也就是所有节点都会进行调整
            siftDown(0,end);
            end--;
        }
    }
}
